package tree;

import exception.NodeIsEmptyException;

import java.util.Comparator;

/**
 * 二叉搜索树
 *
 * @author Europa
 * @create 2020-05-17 23:32
 */
public class SearchTree<T> extends BaseTree<T> {

    private static class BinaryNode<T>{

        /**
         * 树所承载的元素
         */
        T element;

        /**
         * 左子树
         */
        BinaryNode<T> left;

        /**
         * 右子树
         */
        BinaryNode<T> right;

        BinaryNode(T element) {
            this(element, null, null);
        }

        BinaryNode(T element, BinaryNode<T> l, BinaryNode<T> r) {
            this.element = element;
            this.left = l;
            this.right = r;
        }
    }

    /**
     * 根节点
     */
    private BinaryNode<T> root;

    public SearchTree() {
        this(null);
    }

    public SearchTree(Comparator<? super T> compare) {
        root = null;
        super.compare = compare;
    }

    @Override
    public void makeEmpty() {
        root = null;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public boolean contains(T target) {
        return contains(target, root);
    }

    @Override
    public T findMin() {
        if (isEmpty()) {
            throw new NodeIsEmptyException("节点不能为null");
        }
        return findMin(root).element;
    }

    @Override
    public T findMax() {
        if (isEmpty()) {
            throw new NodeIsEmptyException("节点不能为null");
        }
        return findMax(root).element;
    }

    @Override
    public void insert(T target) {
        root = insert(target, root);
    }

    @Override
    public void remove(T target) {
        root = remove(target, root);
    }

    public void printTree() {
        if (isEmpty()) {
            System.out.println("Tree is empty");
        }
        printTree(root);
    }

    /**
     * 查询元素在树中是否存在
     *
     * @param target 搜索目标
     * @param node   树的节点
     * @return 如果找到该项，则为true;否则为false
     */
    private boolean contains(T target, BinaryNode<T> node) {
        if (node == null) {
            return false;
        }
        int compareResult = compare(target, node.element);
        if (compareResult < 0) {
            return contains(target, node.left);
        } else if (compareResult > 0) {
            return contains(target, node.right);
        } else {
            return true;
        }
    }

    /**
     * 寻找最小节点
     *
     * @param node 树的节点
     * @return 包含最小项的节点
     */
    private BinaryNode<T> findMin(BinaryNode<T> node) {
        if (node == null) {
            return null;
        } else if (node.left == null) {
            return node;
        }
        return findMin(node.left);
    }

    /**
     * 寻找最大节点
     *
     * @param node 树的节点
     * @return 包含最大项的节点
     */
    private BinaryNode<T> findMax(BinaryNode<T> node) {
        if (node != null) {
            while (node.right != null) {
                node = node.right;
            }
        }
        return node;
    }

    /**
     * 插入子树的内部方法
     *
     * @param target 要插入的目标
     * @param node   树的节点
     * @return 子树新的根节点
     */
    private BinaryNode<T> insert(T target, BinaryNode<T> node) {
        if (node == null) {
            return new BinaryNode<>(target, null, null);
        }
        int compareResult = compare(target, node.element);
        if (compareResult < 0) {
            node.left = insert(target, node.left);
        } else if (compareResult > 0) {
            node.right = insert(target, node.right);
        }
        return node;
    }

    /**
     * 从子树中移除的内部方法
     *
     * @param target 要删除的目标
     * @param node   树的节点
     * @return 子树新的根节点
     */
    private BinaryNode<T> remove(T target, BinaryNode<T> node) {
        if (node == null) {
            return null;
        }
        int compareResult = compare(target, node.element);
        if (compareResult < 0) {
            node.left = remove(target, node.left);
        } else if (compareResult > 0) {
            node.right = remove(target, node.right);
        } else if (node.left != null && node.right != null) {
            node.element = findMin(node.right).element;
            node.right = remove(node.element, node.right);
        } else {
            node = (node.left != null) ? node.left : node.right;
        }
        return node;
    }

    private void printTree(BinaryNode<T> node) {
        if (node != null) {
            printTree(node.left);
            System.out.println("node.element = " + node.element);
            printTree(node.right);
        }
    }

    private int height(BinaryNode<T> node) {
        if (node == null) {
            return -1;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

//    -------------------------------------------------------

    private static class AvlNode<T> {

        /**
         * 树承载的元素
         */
        T element;

        /**
         * 左子树
         */
        AvlNode<T> left;

        /**
         * 右子树
         */
        AvlNode<T> right;

        /**
         * 树的高度
         */
        int height;

        AvlNode(T element) {
            this(element, null, null);
        }

        AvlNode(T element, AvlNode<T> l, AvlNode<T> r) {
            this.element = element;
            left = l;
            right = r;
        }
    }

    /**
     * 允许不平衡
     */
    private static final int ALLOWED_IMBALANCE = 1;

    /**
     * 获取树的高度
     *
     * @param node 二叉平衡树节点
     * @return 返回节点node的高度，如果为null，则返回-1
     */
    private int getHeight(AvlNode<T> node) {
        return node == null ? -1 : node.height;
    }

    private AvlNode<T> findMin(AvlNode<T> node) {
        if (node == null) {
            return null;
        } else if (node.left == null) {
            return node;
        }
        return findMin(node.left);
    }

    /**
     * 插入AVL子树
     *
     * @param target 要插入的目标
     * @param node   树的节点
     * @return 子树新的根节点
     */
    private AvlNode<T> insert(T target, AvlNode<T> node) {
        if (node == null) {
            return new AvlNode<>(target, null, null);
        }
        int compareResult = compare(target, node.element);
        if (compareResult < 0) {
            node.left = insert(target, node.left);
        } else if (compareResult > 0) {
            node.right = insert(target, node.right);
        }
        return balance(node);
    }

    /**
     * 假设node是平衡的或者在平衡的范围内
     *
     * @param node 二叉平衡树节点
     * @return
     */
    private AvlNode<T> balance(AvlNode<T> node) {
        if (node == null) {
            return null;
        }
        //左子树高度
        int leftHeight = getHeight(node.left);
        //右子树高度
        int rightHeight = getHeight(node.right);
        if (leftHeight - rightHeight > ALLOWED_IMBALANCE) {
            //左子树的左子树高度
            int llh = getHeight(node.left.left);
            //左子树的右子树高度
            int lrh = getHeight(node.left.right);

            if (llh >= lrh) {
                node = rotateWithLeftChild(node);
            } else {
                node = doubleWithLeftChild(node);
            }
        } else if (rightHeight - leftHeight > ALLOWED_IMBALANCE) {
            //右子树的右子树高度
            int rrh = getHeight(node.right.right);
            //右子树的左子树高度
            int rlh = getHeight(node.right.left);

            if (rrh >= rlh) {
                node = rotateWithLeftChild(node);
            } else {
                node = doubleWithLeftChild(node);
            }
        }
        //重新计算左子树高度
        int lh = getHeight(node.left);
        //重新计算右子树高度
        int rh = getHeight(node.right);
        node.height = Math.max(lh, rh) + 1;
        return node;
    }

    /**
     * 旋转左子树(单旋)<br/>
     * 用左子节点旋转二叉树节点。
     * 对于AVL树，这是对case 1的单次旋转。
     * 更新高度，然后返回新的根节点。
     *
     * @param avl 待旋转节点
     * @return 旋转后的节点
     */
    private AvlNode<T> rotateWithLeftChild(AvlNode<T> avl) {
        AvlNode<T> newNode = avl.left;
        avl.left = newNode.right;
        newNode.right = avl;
        //节点的左子树高度
        int avlLeft = getHeight(avl.left);
        //节点的右子树高度
        int avlRight = getHeight(avl.right);
        //重新计算avl的高度
        avl.height = Math.max(avlLeft, avlRight);

        //新节点的左子树高度
        int newLeft = getHeight(newNode.left);
        //更新新节点的高度
        newNode.height = Math.max(newLeft, avl.height);
        return newNode;
    }

    /**
     * 旋转左子树(双旋)<br/>
     * 双旋转二叉树节点:第一个左子节点
     * 和它的右子结点;然后节点k3与新的左子节点。
     * 对于AVL树，这对于case 2是一个双重旋转。
     * 更新高度，然后返回新的根。
     *
     * @param avl
     * @return
     */
    private AvlNode<T> doubleWithLeftChild(AvlNode<T> avl) {
        avl.left = rotateWithLeftChild(avl.left);
        return rotateWithLeftChild(avl);
    }

    /**
     * 寻找最小节点
     *
     * @param node 树的节点
     * @return 包含最小项的节点
     */
    private AvlNode<T> remove(T target, AvlNode<T> node) {
        if (node == null) {
            return null;
        }
        int compareResult = compare(target, node.element);
        if (compareResult < 0) {
            node.left = remove(target, node);
        } else if (compareResult > 0) {
            node.right = remove(target, node);
        } else if (node.left != null && node.right != null) {
            node.element = findMin(node.right).element;
            node.right = remove(node.element, node.right);
        }
        node = (node.left != null) ? node.left : node.right;
        return balance(node);
    }


}
